BZOJ1857【SCOI2010】传送带 <三分法>

Problem

【SCOI2010】传送带

Description

在一个维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段和线段。
在上的移动速度为，在上的移动速度为，在平面上的移动速度。
现在想从点走到点，他想知道最少需要走多长时间。

Input

输入数据第一行是个整数，表示和的坐标，分别为。
第二行是个整数，表示和的坐标，分别为。
第三行是个整数，分别是。

Output

输出数据为一行，表示从点走到点的最短时间，保留到小数点后位。

Sample Input

1
2
3

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

Hint

对于的数据，，。

标签：三分法

Solution

三分套三分，据说有大学物理结论可以做…
首先一定是从走到上的一点，然后走平面到上的一点，最后从沿走到。
考虑确定上的点，那么若将点的所有位置都计算答案并画成函数图像，一定是一个单峰函数。那么确定后可以三分法找到最佳位置。
同样地，对于每个位置的最佳答案，也会呈一个单峰函数。因此可以先对在上进行三分，每次三分到的两个端点需要再对在上进行三分找到最小时间。
这样一来，可以先在上三分，每次三分找端点最值的时候再在上三分，三分套三分即可找到答案。

Code

#include <bits/stdc++.h>
#define EPS 1e-4
#define xx first
#define yy second
#define mp make_pair
#define pdd pair<dnt,dnt>
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
pdd A, B, C, D;	dnt P, Q, R;
dnt sqr(dnt x) {return x*x;}
dnt dis(pdd x, pdd y) {return sqrt(sqr(x.xx-y.xx)+sqr(x.yy-y.yy));}
dnt tri_search_T(pdd l, pdd r, pdd S) {
    dnt ret = dis(A, S)/dis(l, D)/Q+dis(S, l)/R;	pdd llr, lrr;
    while (fabs(l.xx-r.xx) > EPS || fabs(l.yy-r.yy) > EPS) {
        llr = mp(l.xx+(r.xx-l.xx)/3, l.yy+(r.yy-l.yy)/3);
        lrr = mp(r.xx-(r.xx-l.xx)/3, r.yy-(r.yy-l.yy)/3);
        dnt tllr = dis(A, S)/P+dis(llr, D)/Q+dis(S, llr)/R;
        dnt tlrr = dis(A, S)/P+dis(lrr, D)/Q+dis(S, lrr)/R;
        if (tllr < tlrr) r = lrr; else l = llr;
        ret = min(tllr, tlrr);
    }
    return ret;
}
dnt tri_search_S(pdd l, pdd r) {
    dnt ret = tri_search_T(C, D, l);	pdd llr, lrr;
    while (fabs(l.xx-r.xx) > EPS || fabs(l.yy-r.yy) > EPS) {
        llr = mp(l.xx+(r.xx-l.xx)/3, l.yy+(r.yy-l.yy)/3);
        lrr = mp(r.xx-(r.xx-l.xx)/3, r.yy-(r.yy-l.yy)/3);
        dnt tllr = tri_search_T(C, D, llr);
        dnt tlrr = tri_search_T(C, D, lrr);
        if (tllr < tlrr) r = lrr; else l = lrr;
        ret = min(tllr, tlrr);
    }
    return ret;
}
int main() {
    read(A.xx), read(A.yy), read(B.xx), read(B.yy);
    read(C.xx), read(C.yy), read(D.xx), read(D.yy);
    read(P), read(Q), read(R);
    return printf("%.2lf\n", tri_search_S(A, B)), 0;
}